package depthorder;

import entity.TreeNode;

import java.util.*;
public class PostOrderTraversal {
    /*
    * 二叉树的后序遍历
    * 给你二叉树的根节点 root ，返回它节点值的 后序 遍历。
    *
    * 树中节点数目在范围 [0, 100] 内
    * -100 <= Node.val <= 100
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归
    public List<Integer> mySolution(TreeNode root){
        List<Integer> list = new ArrayList<>();
        postOrderTraversal(root, list);
        return list;
    }

    public void postOrderTraversal(TreeNode cur, List<Integer> list){
        if(cur == null)
            return;

        list.add(cur.val);  // 先中
        postOrderTraversal(cur.left, list); // 再左
        postOrderTraversal(cur.right, list); // 再右
    }

    // 迭代
    public List<Integer> solution(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 这个东西用来记录上一个遍历的节点，是判断是否该遍历中节点的重要手段
        TreeNode prev = null;
        // 当前有节点没有遍历完
        while (root != null || !stack.isEmpty()){
            // 先深入到最左叶子节点
            while (root != null){
                stack.add(root);
                root = root.left;
            }
            // 此时root为空 弹栈
            root = stack.pollLast();
            // 判断是不是叶子节点, 或者是不是左右已遍历完的中节点
            if(root.right == null || root.right == prev){
                list.add(root.val);
                // 记录遍历后的节点，用于给下一次遍历提供信息
                prev = root;
                // 制空，这样下次循环就不会向下找，而是直接弹栈
                root = null;
            }
            else { // 该节点还有右儿子
                //  这个节点暂时不能被遍历，还回去
                stack.add(root);
                // 指向右儿子
                root = root.right;
            }
        }
        return list;
    }
}

